package leetcode;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-10
 * Time: 下午5:20
 * To change this template use File | Settings | File Templates.
 */
class TreeLinkNode {
    int val;
    TreeLinkNode left, right, next;
    TreeLinkNode(int x) { val = x; }
}
public class Populating_Next_Right_Pointers_in_Each_Node {
     public static void connect(TreeLinkNode root) {
         TreeLinkNode current = root;


         if(current !=null && current.left!=null){
             current.left.next = current.right;
             TreeLinkNode deepleftR = current.left;
             TreeLinkNode deepRightL = current.right;
             while(deepleftR!=null){                    //关键：以current为root的点往下开始分叉，叉两边的需要在当前层全部连接好。
                 deepleftR = deepleftR.right;
                 deepRightL = deepRightL.left;
                 if(deepleftR!=null){
                     deepleftR.next = deepRightL;
                 }
             }
             connect(current.left);
             connect(current.right);
         }
     }
    public static void main(String[] args){
        TreeLinkNode treeLinkNode1 = new TreeLinkNode(1);
        treeLinkNode1.left = new TreeLinkNode(2);
        treeLinkNode1.left.left = new TreeLinkNode(4);
        treeLinkNode1.left.right = new TreeLinkNode(5);
        treeLinkNode1.left.left.left = new TreeLinkNode(8);
        treeLinkNode1.left.left.right = new TreeLinkNode(9);
        treeLinkNode1.left.right.left = new TreeLinkNode(10);
        treeLinkNode1.left.right.right = new TreeLinkNode(11);

        treeLinkNode1.right = new TreeLinkNode(3);
        treeLinkNode1.right.left = new TreeLinkNode(6);
        treeLinkNode1.right.right = new TreeLinkNode(7);
        treeLinkNode1.right.left.left = new TreeLinkNode(12);
        treeLinkNode1.right.left.right = new TreeLinkNode(13);
        treeLinkNode1.right.right.left = new TreeLinkNode(14);
        treeLinkNode1.right.right.right = new TreeLinkNode(15);
        connect(treeLinkNode1);
        System.out.println(treeLinkNode1.left.left.left.next.val);
       /* System.out.println(treeLinkNode1.left.next.val);
        System.out.println(treeLinkNode1.left.left.val);
        System.out.println(treeLinkNode1.left.right.val);
        System.out.println(treeLinkNode1.right.left.val);
        System.out.println(treeLinkNode1.right.right.val);
        System.out.println(treeLinkNode1.left.left.left.val);
        System.out.println(treeLinkNode1.left.left.right.val);
        System.out.println(treeLinkNode1.left.right.left.val);
        System.out.println(treeLinkNode1.left.right.right.val);
        System.out.println(treeLinkNode1.right.left.left.val);
        System.out.println(treeLinkNode1.right.left.right.val);
        System.out.println(treeLinkNode1.right.right.left.val);
        System.out.println(treeLinkNode1.right.right.right.val);*/

    }
}
